Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 81/115

Q: In a max-heap, element with the greatest key is always in the which node?
A. Leaf node
B. First node of left sub tree
C. root node
D. First node of right sub tree
Solution: This is one of the property of max-heap that root node must have key greater than its children.
Q: What is the complexity of adding an element to the heap.
A. O(log n)
B. O(h)
C. O(log n) & O(h)
D. O(n)
Solution: The total possible operation in re locating the new location to a new element will be equal to height of the heap.
Q: The worst case complexity of deleting any arbitrary node value element from heap is __________
A. O(logn)
B. O(n)
C. O(nlogn)
D. O(n2)
Solution: The total possible operation in deleting the existing node and re locating new position to all its connected nodes will be equal to height of the heap.
Q: Heap can be used as ________________
A. Priority queue
B. Stack
C. A decreasing order array
D. Normal Array
Solution: The property of heap that the value of root must be either greater or less than both of its children makes it work like a priority queue.
Q: An array consists of n elements. We want to create a heap using the elements. The time complexity of building a heap will be in order of
A. O(n*n*logn)
B. O(n*logn)
C. O(n*n)
D. O(n *logn *logn)
Solution: The total time taken will be N times the complexity of adding a single element to the heap. And adding a single element takes logN time, so That is equal to N*logN.
Q: What is the space complexity of searching in a heap?
A. O(logn)
B. O(n)
C. O(1)
D. O(nlogn)
Solution: The space complexity of searching an element in heap is O (n). Heap consists of n elements and we need to compare every element. Here no addition or deletion of elements takes place. Hence space complexity is O (n).
Q: What is the best case complexity in building a heap?
A. O(nlogn)
B. O(n2)
C. O(n*longn *logn)
D. O(n)
Solution: The best case complexity occurs in bottom-up construction when we have a sortes array given.
Q: What is the location of a parent node for any arbitary node i?
A. (i/2) position
B. (i+1)/ position
C. floor(i/2) position
D. ceil(i/2) position
Solution: For any node child nodes are located at either 2*i, 2*i +1 So the parent node could be found by taking the floor of the half of child node.
Q: State the complexity of algorithm given below.

	int function(vector arr)
	int len=arr.length();
	if(len==0)
	return;
	temp=arr[len-1];
	arr.pop_back();
	return temp;
A. o(n)
B. O(logn)
C. O(1)
D. O(n logn)
Solution: Deletion in a min-heap is in O(1) time.
Q: For construction of a binary heap with property that parent node has value less than child node. In reference to that which line is incorrect. Line indexed from 1.

1. add(int k)
2. {
3.     heap_size++;
4.     int i = heap_size - 1;
5.     harr[i] = k;
6.     while (i != 0 && harr[parent(i)] < harr[i])
7.     {
8.             swap(&harr[i], &harr[parent(i)]);
9.             i = parent(i);
10.    }
11. }
A. Line – 3
B. Line – 5
C. Line – 6
D. Line – 7
Solution: The condition under while condition is wrong for a (min) binary heap The correct condition should be while(i!=0 && harr[parent(i)] > harr[i]). Otherwise the constructed heap will be a max-binary heap.

You Have Score    /10